# 方式一:
def quick(arr, i, j):
    start = i
    end = j
    if start > end:
        return
    base = arr[i]
    while start != end:
        while True:
            if end <= start or arr[end] < base:
                break
            end -= 1
        while True:
            if end <= start or arr[start] > base:
                break
            start += 1
        arr[start], arr[end] = arr[end], arr[start]
    arr[i], arr[start] = arr[start], arr[i]
    quick(arr, i, start - 1)
    quick(arr, start + 1, j)


# 方式二：选择排序+递归
def quick02(arr, low, high):
    if low > high:
        return
    i = low - 1
    pivot = arr[high]
    for j in range(low, high):
        if arr[j] < pivot:
            i += 1
            arr[j], arr[i] = arr[i], arr[j]
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    quick02(arr, low, i)
    quick02(arr, i + 2, high)


if __name__ == '__main__':
    array = [100, 23, 45, 12, 25, 3, 90, 34]
    quick02(array, 0, len(array) - 1)
    print(array)
